/*
 * Problem:
 *     given a binary tree as follows:
 *         struct TreeNode {
 *             struct TreeNode *left;
 *             struct TreeNode *right;
 *             int element;
 *         }
 *     find whether existing a path from root to leaf that the sum of elements
 *     in this path equals to a given value?
 *
 * Points:
 *     backtrack
 */
#include<stdio.h>
typedef int Element;
struct TreeNode {
	Element element;
	struct TreeNode *left;
	struct TreeNode *right;
};

int sum=0;
int find=0;
int path[100];
int depth=0;

void
findpath(struct TreeNode *root, int value)
{
	if(root->right==NULL && root->left==NULL) {
		if(sum+root->element==value) {
			find += 1;
			int i;
			path[depth++] = root->element;
			for(i=0; i<depth; i++)
				printf("%d\t", path[i]);
			printf("\n");
			depth--;
		}
		return;
	}

	sum += root->element;
	path[depth++] = root->element;
	if(root->left != NULL)
		findpath(root->left, value);
	if(root->right != NULL)
		findpath(root->right, value);
	sum -= root->element;
	depth--;
}

/*
 * 理解回溯
 * 回溯通过递归来实现，这里两次递归本身就包含着回溯的过程
 * 回溯是一个尝试-失败-再尝试的过程
 */
int
findpath_minus(struct TreeNode *root, int value)
{
	if(root->left==NULL && root->right==NULL) {
		if(value == root->element)
			return 1;
		else
			return 0;
	}
	if(findpath_minus(root->left, value-(root->element)))
		return 1; /* 减枝 */
	else
		return findpath_minus(root->right, value-(root->element));
}

/* ------------------test------------------------ */
int 
main(int argc, char **argv)
{
	struct TreeNode a, b, c, d, e, f, g, h;
	a.element = 5;
	a.left = &b;
	a.right = &c;

	b.element = 3;
	b.left = &d;
	b.right = &e;

	c.element = 4;
	c.left = &f;
	c.right = &g;

	d.element = 7;
	d.left = d.right = NULL;

	e.element = 1;
	e.left = &h;
	e.right = NULL;

	f.element = 8;
	f.left = f.right = NULL;

	g.element = 2;
	g.left = g.right = NULL;

	h.element = 2;
	h.left = h.right = NULL;

	sum = 0;
	find = 0;
	findpath(&a, 11);

	printf("find: %d\n", find);
	printf("find-minus: %d\n", findpath_minus(&a, 11));
}
